/*
day319 
2020.7.12 
*/

#include<iostream>
#include<cstdlib>
#include<unordered_map>
#include<vector>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
    	int res=0;
		int *arr=new int[nums.size()+1];
		arr[0]=0;
		for(int i=0;i<nums.size();++i)
		{
			arr[i+1]=arr[i]+nums[i];
		}
		
		for(int i=1;i<=nums.size();++i)
		{
			for(int j=i;j<=nums.size();++j)
			{
				
				if(arr[j]-arr[i-1]==k)
				{
					res++;
				 } 
			}
		}
		
		return res;
    }
};

class Solution2 {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto& x:nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) count += mp[pre - k];
            mp[pre]++;
        }
        return count;
    }
};


int main()
{
	return 0;
 } 
